package class04;

/**
 * 题目：构造达标数组
 * 
 * 描述：
 * 给定一个正整数N，构造一个长度为N的数组，满足对于任意的下标 i<k<j，
 * 都有 arr[i] + arr[j] != arr[k] * 2
 * 
 * 解题思路：
 * 使用分治法解决该问题。对于长度为N的数组，将其分为两部分：
 * 1. 前半部分放置奇数位置的元素
 * 2. 后半部分放置偶数位置的元素
 * 
 * 具体做法是递归构造一半大小的达标数组，然后通过变换得到原数组：
 * - 将基础数组的每个元素乘以2再减1，得到奇数序列
 * - 将基础数组的每个元素乘以2，得到偶数序列
 */
public class Code06_MakeNo {

	// 生成长度为size的达标数组
	// 达标：对于任意的 i<k<j，满足 [i] + [j] != [k] * 2
	public static int[] makeNo(int size) {
		if (size == 1) {
			return new int[] { 1 };
		}
		// size
		// 一半长达标来
		// 7 : 4
		// 8 : 4
		// [4个奇数] [3个偶]
		int halfSize = (size + 1) / 2;
		
		// 递归获取一半长度的达标数组作为基础数组
		int[] base = makeNo(halfSize);
		
		// base -> 等长奇数达标来
		// base -> 等长偶数达标来
		int[] ans = new int[size];
		int index = 0;
		
		// 将基础数组转换为奇数序列，放入结果数组前半部分
		for (; index < halfSize; index++) {
			ans[index] = base[index] * 2 - 1;
		}
		
		// 将基础数组转换为偶数序列，放入结果数组后半部分
		for (int i = 0; index < size; index++, i++) {
			ans[index] = base[i] * 2;
		}
		return ans;
	}

	// 检验函数
	public static boolean isValid(int[] arr) {
		int N = arr.length;
		for (int i = 0; i < N; i++) {
			for (int k = i + 1; k < N; k++) {
				for (int j = k + 1; j < N; j++) {
					if (arr[i] + arr[j] == 2 * arr[k]) {
						return false;
					}
				}
			}
		}
		return true;
	}

	public static void main(String[] args) {
		System.out.println("test begin");
		for (int N = 1; N < 1000; N++) {
			int[] arr = makeNo(N);
			if (!isValid(arr)) {
				System.out.println("Oops!");
			}
		}
		System.out.println("test end");
		System.out.println(isValid(makeNo(1042)));
		System.out.println(isValid(makeNo(2981)));
	}

}
